/**
 * Created with Intellij JDEA
 * Description:
 * User:
 * Date:2022-05-25
 * Time:15:24
 */
class N {
    public int val;
    public N left;
    public N right;
    public N[] children;

    public N() {}

    public N(int _val) {
        val = _val;
    }

    public N(int _val, N _left, N _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
public class 二叉搜索树与双向链表 {
    class Solution {
        N pre, head;
        public N treeToDoublyList(N root) {
            if(root == null) return null;
            dfs(root);
            head.left = pre;
            pre.right = head;
            return head;
        }
        void dfs(N cur) {
            if(cur == null) return;
            dfs(cur.left);
            if(pre != null) {
                pre.right = cur;
            }
            else {
                head = cur;
            }
            cur.left = pre;
            pre = cur;
            dfs(cur.right);
        }
    }
}
